package com.cqs.leetcode.tree;

import com.cqs.leetcode.ListNode;
import com.cqs.leetcode.TreeNode;

/**
 * @author lixqw
 * @date 2020/8/18
 */
public class ConvertSortedListtoBinarySearchTree109 {

    /**
     * @param head
     * @return
     */
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode pre = null, slow = head, fast = head.next;
        while (fast != null) {
            pre = slow;
            slow = slow.next;
            //forward two steps
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }
        TreeNode root = new TreeNode(slow.val);
        root.right = sortedListToBST(slow.next);
        slow.next = null;
        pre.next = null;
        root.left = sortedListToBST(head);
        return root;
    }
}
